#include <iostream>
#include <string>
using namespace std;
// 带头结点的链表队列
class Queue {
   struct Node {
       char val;
       Node* next;
       Node() : val{}, next{nullptr} {}
       Node(char _val) : val{_val}, next{nullptr} {}
   };
   Node* dummy = new Node;
   Node* tail = dummy;
public:
   Queue() {}
   Queue(string s) {
       for (const auto& c : s) {
           enQueue(c);
       }
   }
   ~Queue() {
       for (Node* cur = dummy, * nxt; cur; cur = nxt) {
           nxt = cur->next;
           delete cur;
       }
   }

   bool empty() {
       return not dummy->next;
   }

   void enQueue(char val) {
       tail->next = new Node(val);
       tail = tail->next;
   }

   char deQueue() {
       if (empty()) {
           perror("empty!\n");
           return -1;
       }
       Node* node = dummy->next;
       char res = node->val;
       dummy->next = node->next;
       delete node;
       return res;
   }

   char top() {
       return dummy->next->val;
   }
};

int main() {
    Queue q;
    q.enQueue('a');
    q.enQueue('b');
    q.enQueue('c');
    q.enQueue('d');
    q.enQueue('e');
    q.enQueue('f');
    cout << q.deQueue() << endl;
    cout << q.deQueue() << endl;
    cout << q.deQueue() << endl;
    cout << q.deQueue() << endl;
    cout << q.deQueue() << endl;
    cout << q.deQueue() << endl;
    cout << q.deQueue() << endl;
}
